/// @tags: NTT PrimitiveRoot
#include <cstdio>
#include <cstring>
#include <iostream>
#define rint register int

using std::cin;
using std::cout;

namespace BlueQuantum {

typedef long long LL;

const int p = 1004535809, maxm = 8e3 + 3, maxlen = 1 << 14;

inline LL qpow(LL base, int exp = p - 2) {
  LL res = 1;
  for (; exp; exp >>= 1, base = base * base % p)
    if (exp & 1) res = res * base % p;
  return res;
}

struct Polynomial {
  static int n;
  static int cvt[maxlen];
  int f[maxlen];

  inline int& operator[](int index) { return f[index]; }
  inline const int& operator[](int index) const { return f[index]; }

  inline Polynomial(int x = 0) {
    memset(f, 0, sizeof(f));
    f[0] = x;
  }

  static inline void init() {
    int maxl = 1;
    while (maxl < n + n + 1) maxl <<= 1;
    for (int i = 1; i < maxl; ++i) {
      cvt[i] = cvt[i >> 1] >> 1 | (i & 1) * (maxl >> 1);
    }
  }

  inline void ntt(int maxl, int typ) {
    const int g = 3, invg = 334845270;
    for (int i = 1; i < maxl; ++i) {
      if (i < cvt[i]) std::swap(f[i], f[cvt[i]]);
    }
    for (int i = 2; i <= maxl; i <<= 1) {
      int mid = i >> 1, w = qpow(typ ? g : invg, (p - 1) / i);
      for (int j = 0; j < maxl; j += i) {
        LL wk = 1;
        for (int k = 0; k < mid; ++k, wk = wk * w % p) {
          LL tmp = f[j + k + mid] * wk % p;
          f[j + k + mid] = (f[j + k] - tmp + p) % p;
          (f[j + k] += tmp) %= p;
        }
      }
    }
    if (typ == 0) {
      LL inv = qpow(maxl);
      for (int i = 0; i < maxl; ++i) f[i] = f[i] * inv % p;
    }
  }

  inline Polynomial operator*(const Polynomial& rhs) const {
    Polynomial res, a(*this), b(rhs);
    int maxl = 1;
    while (maxl < n + n + 1) maxl <<= 1;
    a.ntt(maxl, true), b.ntt(maxl, true);
    for (int i = 0; i < maxl; ++i) res[i] = (LL)a[i] * b[i] % p;
    res.ntt(maxl, false);
    for (int i = n + 1; i <= n + n; ++i) {
      (res[i - n - 1] += res[i]) %= p;
      res[i] = 0;
    }
    return res;
  }

  inline Polynomial operator^(int exp) const {
    Polynomial res(1), base(*this);
    for (; exp; exp >>= 1, base = base * base)
      if (exp & 1) res = res * base;
    return res;
  }
} F;

int Polynomial::n;
int Polynomial::cvt[maxlen];

inline bool checkG(int x, int m) {
  static int cnt[maxm];
  memset(cnt, 0, sizeof(cnt));
  int exp = 1;
  for (int i = 0; i < m - 1; ++i) {
    cnt[exp]++;
    if (cnt[exp] > 1) return false;
    exp = exp * x % m;
  }
  return true;
}

inline int getG(int m) {
  for (int i = 2; i < m; ++i)
    if (checkG(i, m)) return i;
  return 0;
}

int lg[maxm];

inline void getLg(int g, int m) {
  for (int i = 0, exp = 1; i < m - 1; ++i) {
    lg[exp] = i;
    (exp *= g) %= m;
  }
}

inline int main() {
  int n, m, x, S;
  cin >> n >> m >> x >> S;
  int g = getG(m);
  getLg(g, m);
  Polynomial::n = m - 2;
  Polynomial::init();
  for (int i = 1, s; i <= S; ++i) {
    cin >> s;
    if (s != 0) F[lg[s]]++;
  }
  cout << (F ^ n)[lg[x]];
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("P3321 [SDOI2015] 序列统计.in", "r", stdin);
  freopen("P3321 [SDOI2015] 序列统计.out", "w", stdout);
#endif
#endif

  std::ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
